﻿/*
	红黑树是一棵二叉搜索树，他的每个结点增加一个存储位来表示结点的颜色，可以是红色或者黑色。
通过对任何一条从根到叶子的路径上各个结点的颜色进行约束，红黑树确保没有一条路径会比其他路
径长出2倍，因而是接近平衡的。

红黑树规则：
	1. 每个结点不是红色就是黑色
	2. 根结点是黑色的
	3. 如果一个结点是红色的，则它的两个孩子结点必须是黑色的，也就是说任意一条路径不会有连续的红色结点
	   (没有  红红节点  一说)
	4. 对于任意一个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的黑色结点
	   (从根开始每条路径黑色节点的数量都是相等)


	*  路径的意思是从根节点开始    走到空

	极端的场景：
	   假设每一条路径有X个黑色节点
	   那么他的最短路径就有：X       全黑
			   最长路径就有：2*X     一黑一红的情况


红黑树确保没有一条路径会比其他路径长出2倍     为什么？
	1.极端场景下，最短路径就是全是黑色结点的路径，假设最短路径长度为bh
	2.任意一条路径不会有连续的红色结点，极端场景下，最长的路径就是一黑一红间隔组成，那么最长路径的长度为  2*bh
	3.理论上的全黑最短路径和一黑一红的最长路径并不是在每棵红黑树都存在的。
	  假设任意一条从根到NULL结点路径的长度为x，那么bh <= h <= 2*bh

红黑树的效率
	1.假设N是红黑树树中节点数量，h是最短路径的长度，2^h-1 <= 2^2*h-1,推出 h 近似等于logN，也就是说红黑树增删改查最坏也就是走
	  2*logN，时间复杂度还是O(logN)
	2.红黑树表达相对AVL抽象，AVL通过高度差直观控制平衡，红黑树四条规则的颜色约束，间接实现近似平衡，效率同一档次，相对说，插入
	  相同数量节点，红黑树的旋转次数更少，因为平衡控制没有那么严格


红黑树树插入一个值的大概过程
	1.插入一个值按二叉搜索树规则进行插入，插入后只需观察是否符合红黑树四条规则
	2.如果是空树插入，新增结点是黑色结点。如果是非空树插入，新增结点必须红色结点，因为非空树
	  插入，新增黑色结点就破坏了规则4，规则4是很难维护的。
	3.非空树插入后，新增结点必须红色结点，如果父亲结点是黑色的，则没有违反任何规则，插入结束
	4.非空树插入后，新增结点必须红色结点，如果父亲结点是红色的，则违反规则3。进一步分析，c是
	  红色，p为红，g必为黑，这三个颜色都固定了，关键的变化看u的情况，需要根据u分情况分别处理。

新增节点表示为 c(cur)     c父亲节点表示为p(parent)     p的父亲表示为g(grandfather)     
p的兄弟表示为u（uncle）   只有u（uncle） 的情况颜色是不确定的
（但是无论如何走    都需要把父亲变黑）

情况1：（只变色）
	  c为红，p为红，g为黑，u存在且为红，则将p和u变黑，g变红。再把g当做新的c，继续往上更新
原因：p和u都是红色，g是黑色，把p和u变黑，左边子树路径各增加一个黑色结点，g再变红，相当于保持g所在子树的黑色结点的数量不变，
	  同时解决了c和p连续红色结点的问题，需要继续往上更新是因为，g是红色，如果g的父亲还是红色，那么就还需要继续处理；
	  如果g的父亲是黑色，则处理结束了; 如果g就是整棵树的根，再把g变回黑色。
情况1只变色，不旋转。所以无论c是p的左还是右，p是g的左还是右，都是上面的变色处理方式。



情况2：（单旋+变色）
c为红，p为红，g为黑，u不存在或者u存在且为黑
u不存在，则c一定是新增结点，
u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。
（分两种小情况(1).叔叔不存在，cur一定是新增   (2).叔叔存在且为黑那么cur一定不是新增，cur之前是黑色,在c子树中插入）

p必须变黑，才能解决，连续红色结点的问题，u不存在或者是黑色的，这里单纯的变色无法解决问题，需要   旋转+变色



情况3：(双旋+变色)
c为红，p为红，g为黑，u不存在或者u存在且为黑，
u不存在，则c一定是新增结点，
u存在且为黑，则c一定不是新增，c之前是黑色的，是在c的子树中插入，符合情况1，变色将c从黑色变成红色，更新上来的。


红黑树的验证
	1. 规则1枚举颜色类型，保证了颜色不是黑色就是红色。
	2. 规则2直接检查根即可
	3. 规则3前序遍历检查，遇到红色结点查孩子不太方便，因为孩子有两个，且不一定存在，反过来检
	   查父亲的颜色就方便多了。
	4. 规则4前序遍历，遍历过程中用形参记录跟到当前结点的blackNum(黑色结点数量)，前序遍历遇到
	   黑色结点就 ++blackNum，走到空就计算出了一条路径的黑色结点数量。再任意一条路径黑色结点
	   数量作为参考值，依次比较即可。
*/